1. Field of the Invention
The present invention generally relates to compressed memory and compressed disk systems, and, more specifically, to a method for transferring memory compressed data to and from the disk adapter, and for storing memory compressed data on disk, thereby obviating the need to decompress and recompress data when transferring between memory and disk, and thus saving time and bandwidth in the system.
2. Description of the Related Art
Main Memory Compression
An emerging development in computer organization is the use of data compression in a computer system's main memory, where the data in the main memory is stored in a compressed format. For example, FIG. 1 shows the overall structure of an exemplary computer system 100 implementing a compressed main memory 110.
In FIG. 1, a central processing unit (CPU) 102 reads data to and writes data from a cache 104. Cache “misses” and “stores” result in reads and writes to a compressed main memory 110 by a compression controller 106.
That is, typically the CPU will obtain the data from the cache 104 (e.g., assuming a cache “hit”), whereas on a cache “miss” the CPU will obtain the data from the main memory 110 through the compression controller 106. Such data would be retrieved to the CPU and then the data would be stored to the cache 104 (e.g., typically a so-called “store-through” cache, which is one of the most common caching techniques).
The compressed main memory 108 is typically divided into a number of logically fixed-size segments (e.g., segments spanning a range of contiguous memory addresses). These logical segments are the units of compression and are referred to as “memory lines”. Memory lines are physically stored in a compressed format, and therefore occupy a variable number of physical memory locations. There are several proposed computer system designs where the contents of main memory is compressed, including U.S. Pat. No. 5,761,536, entitled “System and Method for Reducing Memory Fragmentation by Assigning Remainders to Share Memory Blocks on a Best Fit Basis” and Franaszek et al., “Design and Analysis of Internal Organizations for Compressed Random Access Memories”, IBM Research Report RC 21146, IBM Watson Research Center, Mar. 30, 1998 (revised Oct. 9, 1998).
In a paged memory system, the unit of memory management is a “page”, usually consisting of 4096 bytes having consecutive real addresses, aligned on a 4096 byte boundary. The unit of compression can be any size and in some systems the unit of compression is a page.
To simplify management of the compressed memory system, it is better to select the size of the unit of compression (called a “line”) so that the uncompressed size of a page is a multiple of the uncompressed size of a line. A page is then divided into a fixed number of lines, and the bytes of a line are compressed and decompressed together. Hereinbelow, it will be assumed that an uncompressed line is 1024 bytes long.
Compressing a line produces a variable-size compressed line (e.g., different lines will compress to different numbers of bytes). The compressed size of a line is an important parameter, which is needed for physical memory management. If a line that does not compress to less than its original size is left uncompressed, one needs (1+log(n)) bits to describe the size of the compressed line, where n is the original size in number of bytes, and the logarithm is base 2.
To simplify management, the size of a compressed line can be constrained to be a multiple of a fixed number of bytes, for instance by “padding” the compressed line with zeros. The term “granule” is used to denote the atomic size of compressed data. The granule size should be a divider of the line size.
FIG. 2 shows, in more detail, an architecture 200 of a compressed main memory system 210. The architecture 200 includes a cache 240, containing cache lines 241 and a cache directory 242, the compression controller 260, containing a compressor 261 and a decompressor 262, and compressed main memory 210. The compressed main memory 210 includes a directory 220 and a number of fixed sized blocks 230, also called “memory sectors”. The above exemplary format and organization is what is referred to as “main memory compressed data.”
As shown in FIG. 2, for a read from the compressed memory to the cache, the decompressor 262 is employed, whereas on a write from the cache to the compressed main memory, the line must be compressed via the compressor 261. As known, lines in the cache are similarly held in the main memory. Along these lines, if a line must be evicted from the cache (e.g., the cache capacity is exhausted), then the cache line being evicted is written back to the compressed main memory 210 via the compressor 261 if modified.
If a cache line associated with address A is not found in the cache 240, then this address A 270 is used to index into the directory D 220. This is different from a conventional computer system where the address is used to directly reference a location in the memory M 210.
Each directory entry contains information which allows the associated cache line to be retrieved. The units of compressed data referred to by directory entries in D 220 may correspond to cache lines 241, or the unit of compression may be larger than a cache line in which case multiple cache lines would be compressed together into one unit of compression.
The directory entry 221 for line 1 associated with address A1 271 is for a line which has been compressed to a degree in which the compressed line can be stored entirely within the directory entry. Lines A2 272, A3 273, and A4 274 in FIG. 2 do not compress sufficiently to be stored in a directory entry, and therefore they are stored in an integer number of memory sectors.
The directory entry 222 for line 2 associated with address A2 272 is for a line which is stored in compressed format using a first full memory sector 231 and second partially filled memory sector 232.
Finally, the directory entries 223 and 224 for line 3 and line 4 associated with addresses A3 273 and A4 274 are for lines stored in compressed formats using a number of full memory sectors (2 sectors 233 and 234 for line 3, and no sector for line 4) and in which the remainders of the two compressed lines have been combined in block 235. Memory-sector sharing by different lines within a page (or across pages) is done to reduce fragmentation, and in this situation, lines sharing a memory sector are called roommates.
FIG. 3 shows some examples of directory (220) entry formats, which can be used in the directory 220 of the main memory system 210 of FIG. 2. For this example, it is assumed that the memory sectors 230 of FIG. 2 are of size 256 bytes, and that the cache lines 241 of FIG. 2 are of size 1024 bytes. Hence, lines can be stored in an uncompressed format using four memory sectors.
For this example, directory entries of size 16 bytes are used, in which the first byte includes a number of flags. The contents of the first byte 301 determines the format of the remainder of the directory entry.
A flag bit 302 specifies whether the line is stored in compressed or uncompressed format. If stored in uncompressed format, then the remainder of the directory entry is interpreted as for line 1 306, in which four 30-bit addresses give the addresses in memory of the four memory sectors containing the line.
If stored in a compressed format, then a flag bit 303 indicates whether the compressed line is stored entirely within the directory entry. If so, then the format of the directory entry is as for line 3 308, in which up to 120 bits of compressed data are stored. Otherwise, for compressed lines longer than 120 bits, the formats shown for line 1 306 or line 2 307 may be used.
In the case of the line 1 306 format, additional flag bits 304 specify the number of blocks used to store the compressed line, from one to four 30-bit addresses specify the locations of the sectors, and finally the size of the remainder, or fragment, of the compressed line stored in the last memory sector (in units of 32 bytes), together with a bit indicating whether the fragment is stored at the beginning or at the end of the memory sector, is given by four fragment information bits 305.
Directory entry format 307 illustrates an alternative format in which part of the compressed line is stored in the directory entry (to reduce decompression latency). In this case, addresses to only the first and last sectors used to store the remaining part of the compressed line are stored in the directory entry, with intervening sectors (if any) found using a linked list technique. That is, each sector used to store the compressed line has, if required, a pointer field containing the address of the next memory sector used to store the given compressed line.
Thus, many different formats may be used in the directory 220 for the compressed main memory according to the decompression/compression of the data.
Disk Compression
Another problem arises in disk systems in going from the disk to the main memory and trying to individually access compressed pages on the disk as opposed to accessing compressed data in the main memory. Indeed, typically the disk and main memory employ two different compression systems having different formats. As a result, compressed data from the main memory must be decompressed and then sent to the disk system where it is recompressed again, and vice versa. Thus, there has been no facility to take compressed data from the disk and place it directly onto the main memory, where the compressed data can then be referenced as described above as compressed main memory data.
In some disk systems, such as the IBM AS/400 DASD® adapter, pages are stored in compressed form to improve the price/capacity ratio. Typically, individual pages (or groups of pages) are compressed into a variable number of fixed-length blocks, called “disk sectors”.
FIG. 4 shows the structure of the UO processor (IOP) 400 and how it is attached to the rest of the system, and more specifically is a high-level representation of an Input/output adaptor (IOA) 405 and the input/output processor 400.
Generally, it is shown that one side is connected back to the system and the other side will be connected to the disk system, and the IOP 400 generally has its own compressor/decompressor 403. That is, data that is being stored on the disks will be compressed in the IOP since the information from the main memory does not come already compressed from the main memory.
The operation of the IOP 400 is controlled by the IOP processor complex 402, which communicates with the main system over a system bus 406 through a system bus to IOA bus adapter 401. The IOP 400 has a local memory 404. If the IOP supports compression in hardware, it contains a compressor/decompressor subsystem 403. The IOP controls one or more IOA adapters 405, which provides an interface with the direct access storage disk (DASD) over a DASD bus 407.
In a compressed disk, the unit of compression is typically a page (e.g. 4096 bytes), which is also the atomic unit of UO. Physical space on disks is managed in atomic units called sectors. A disk sector typically contains 512 bytes of data and can contain additional information such as cyclic redundancy code (CRC) bytes and system headers.
When a page is written to a compressed disk, it is first compressed, and the resulting compressed page is stored in an integer number of disk sectors.
Several approaches to managing and organizing compressed disks are possible, which rely on different directory data structures.
From the description of the conventional techniques, it is clear that the organization of a compressed disk and of a compressed memory are usually very different. This is the case, for instance, when the disk subsystem is separate from the computing units (as in Enterprise Storage servers such as SHARK® or EMC® disk servers), or when the two technologies are developed separately (as would be the case for AS/400® machines supporting memory compression and using the current disk adapter.)
Since the structures that have been created to support memory compression and disk compression are quite different, some inefficiencies arise when a system supporting memory compression operates with a compressed disk.
For example, when data is transferred from memory to disk and from disk to memory, the data must first be decompressed, then transferred, and then recompressed, as mentioned above.
In principle, data could be transmitted in compressed form to and from the disk. This would not only obviate the need to perform additional compressions and decompressions, but it would also effectively increase the bandwidth of the links.
Additionally, if the data is transmitted from memory to disk adapter in compressed format, then the disk adapter would know in advance the size of the data, and would be able to make better storage management decisions. In contrast, in current compressed disk systems, the disk adapter allocates storage based on how it expects the data to compress.
However, transmitting such compressed data directly to disk without additional and costly steps of decompression and recompression requires changes to the UO operations and the system structure. These changes are the subject of the present invention.